{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Bag of Tokens"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #two-pointers #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #双指针 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: bagOfTokensScore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #令牌放置"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你的初始 <strong>能量</strong> 为 <code>power</code>，初始 <strong>分数</strong> 为&nbsp;<code>0</code>，只有一包令牌 <code>tokens</code> 。其中 <code>tokens[i]</code> 是第 <code>i</code> 个令牌的值（下标从 0 开始）。</p>\n",
    "\n",
    "<p>令牌可能的两种使用方法如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果你至少有&nbsp;<code>token[i]</code>&nbsp;点 <strong>能量</strong> ，可以将令牌 <code>i</code> 置为正面朝上，失去&nbsp;<code>token[i]</code>&nbsp;点 <strong>能量</strong> ，并得到&nbsp;<code>1</code>&nbsp;<strong>分</strong> 。</li>\n",
    "\t<li>如果我们至少有&nbsp;<code>1</code>&nbsp;<strong>分 </strong>，可以将令牌 <code>i</code> 置为反面朝上，获得&nbsp;<code>token[i]</code> 点 <strong>能量</strong> ，并失去&nbsp;<code>1</code>&nbsp;<strong>分</strong> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>每个令牌 <strong>最多</strong> 只能使用一次，使用 <strong>顺序不限</strong> ，<strong>不需</strong> 使用所有令牌。</p>\n",
    "\n",
    "<p>在使用任意数量的令牌后，返回我们可以得到的最大 <strong>分数</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>tokens = [100], power = 50\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>无法使用唯一的令牌，因为能量和分数都太少了。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>tokens = [100,200], power = 150\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>令牌 0 正面朝上，能量变为 50，分数变为 1 。\n",
    "不必使用令牌 1 ，因为你无法使用它来提高分数。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>tokens = [100,200,300,400], power = 200\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>按下面顺序使用令牌可以得到 2 分：\n",
    "1. 令牌 0 正面朝上，能量变为 100 ，分数变为 1\n",
    "2. 令牌 3 正面朝下，能量变为 500 ，分数变为 0\n",
    "3. 令牌 1 正面朝上，能量变为 300 ，分数变为 1\n",
    "4. 令牌 2 正面朝上，能量变为 0 ，分数变为 2</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= tokens.length &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= tokens[i],&nbsp;power &lt; 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [bag-of-tokens](https://leetcode.cn/problems/bag-of-tokens/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [bag-of-tokens](https://leetcode.cn/problems/bag-of-tokens/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[100]\\n50', '[100,200]\\n150', '[100,200,300,400]\\n200']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        # 贪心\n",
    "        tokens.sort()\n",
    "        l = 0\n",
    "        r = len(tokens) - 1\n",
    "        score = 0\n",
    "        while l <= r:\n",
    "            if tokens[l] <= power:\n",
    "                power -= tokens[l]\n",
    "                l += 1\n",
    "                score += 1\n",
    "            else:\n",
    "                if score > 0 and power + tokens[r] >= tokens[l]:\n",
    "                    power += tokens[r] - tokens[l]\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens.sort()\n",
    "        l = 0\n",
    "        r = len(tokens)-1\n",
    "        res = 0\n",
    "        ress = 0\n",
    "        while l<=r:\n",
    "            if power<tokens[l]:\n",
    "                if res>0 and l<r:\n",
    "                    res-=1\n",
    "                    power+=tokens[r]\n",
    "                    r-=1\n",
    "                else:\n",
    "                    return res\n",
    "            else:\n",
    "                power-=tokens[l]\n",
    "                res+=1\n",
    "                # ress = max(ress,res)\n",
    "                l+=1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        if tokens == []  or power < sorted(tokens)[0]:\n",
    "            return 0\n",
    "        tokens.sort()\n",
    "        ans = 0\n",
    "        l, r= 0, len(tokens) - 1\n",
    "        while l < r - 1:\n",
    "            while power >= tokens[l]:\n",
    "                power -= tokens[l]\n",
    "                l += 1\n",
    "                ans += 1\n",
    "            if l < r - 1:\n",
    "                power = power + tokens[r] - tokens[l]\n",
    "                r -= 1\n",
    "                l += 1\n",
    "        return ans if power < tokens[l] else ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def bagOfTokensScore(self, tokens, P):\n",
    "        tokens.sort()\n",
    "        deque = collections.deque(tokens)\n",
    "        ans = bns = 0\n",
    "        while deque and (P >= deque[0] or bns):\n",
    "            while deque and P >= deque[0]:\n",
    "                P -= deque.popleft()\n",
    "                bns += 1\n",
    "            ans = max(ans, bns)\n",
    "\n",
    "            if deque and bns:\n",
    "                P += deque.pop()\n",
    "                bns -= 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens.sort()\n",
    "        n = len(tokens)\n",
    "        res, cur = 0, 0\n",
    "        l, r = 0, n - 1\n",
    "        while l <= r and power > tokens[l]:\n",
    "            # print(l, r)\n",
    "            while l <= r and power >= tokens[l]:\n",
    "                power -= tokens[l]\n",
    "                cur += 1\n",
    "                l += 1\n",
    "\n",
    "            res = max(res, cur)\n",
    "            if l <= r and cur:\n",
    "                power += tokens[r]\n",
    "                cur -= 1\n",
    "                r -= 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens.sort()\n",
    "        left, right = 0, len(tokens) - 1\n",
    "        score = 0\n",
    "        max_score = 0\n",
    "\n",
    "        while left <= right:\n",
    "            # 如果当前能量足够，使用最小的令牌获取分数\n",
    "            if power >= tokens[left]:\n",
    "                power -= tokens[left]\n",
    "                score += 1\n",
    "                max_score = max(max_score, score)\n",
    "                left += 1\n",
    "            # 否则，如果我们有分数，翻转最大的令牌获取能量\n",
    "            elif score > 0:\n",
    "                power += tokens[right]\n",
    "                score -= 1\n",
    "                right -= 1\n",
    "            # 如果没有分数也没有足够的能量，结束循环\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return max_score\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens.sort()\n",
    "        n = len(tokens)\n",
    "        res, cur = 0, 0\n",
    "        l, r = 0, n - 1\n",
    "        while l <= r and (power > tokens[l] or cur):\n",
    "            # print(l, r)\n",
    "            while l <= r and power >= tokens[l]:\n",
    "                power -= tokens[l]\n",
    "                cur += 1\n",
    "                l += 1\n",
    "\n",
    "            res = max(res, cur)\n",
    "            if l <= r and cur:\n",
    "                power += tokens[r]\n",
    "                cur -= 1\n",
    "                r -= 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens.sort()\n",
    "        n = len(tokens)\n",
    "        s = 0\n",
    "        p = n-1\n",
    "        maxx = 0\n",
    "        curr = 0\n",
    "        while s <= p:\n",
    "            if power >= tokens[s]:\n",
    "                curr += 1\n",
    "                power -= tokens[s]\n",
    "                s += 1\n",
    "                maxx = max(maxx, curr)\n",
    "            elif curr >= 1:\n",
    "                power += tokens[p]\n",
    "                curr -= 1\n",
    "                p -= 1\n",
    "            else:\n",
    "                break\n",
    "        return maxx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def bagOfTokensScore(self, tokens, power):\n",
    "        tokens.sort()\n",
    "        deque = collections.deque(tokens)\n",
    "        res = score = 0\n",
    "        while deque and (power >= deque[0] or score):\n",
    "            while deque and power >= deque[0]:\n",
    "                power -= deque.popleft()\n",
    "                score += 1\n",
    "            res = max(res, score)\n",
    "            if deque and score:\n",
    "                power += deque.pop()\n",
    "                score -= 1\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens.sort()\n",
    "        now_power = power\n",
    "        now_score = 0\n",
    "        start_point = 0\n",
    "        end_point = len(tokens) - 1\n",
    "        result = 0\n",
    "        if len(tokens) == 0:\n",
    "            return result\n",
    "        if end_point == start_point:\n",
    "            return 1 if power > tokens[0] else 0\n",
    "        while start_point <= end_point:\n",
    "            if now_power < tokens[start_point] and now_score > 0:\n",
    "                now_power += tokens[end_point]\n",
    "                now_score -= 1\n",
    "                end_point -= 1\n",
    "                continue\n",
    "            if now_power >= tokens[start_point]:\n",
    "                now_power -= tokens[start_point]\n",
    "                start_point += 1\n",
    "                now_score += 1\n",
    "                result = max(now_score, result)\n",
    "                continue\n",
    "            break\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        n = len(tokens)\n",
    "        tokens.sort()\n",
    "        ans = 0\n",
    "        l, r = 0, n - 1\n",
    "        while l < r:\n",
    "            if power >= tokens[l]:\n",
    "                ans += 1\n",
    "                power -= tokens[l]\n",
    "                l += 1\n",
    "            else:\n",
    "                if ans:\n",
    "                    power += tokens[r]\n",
    "                    ans -= 1\n",
    "                    r -= 1\n",
    "                else: break\n",
    "\n",
    "        if l == r and power >= tokens[l]:\n",
    "            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens.sort()\n",
    "        left = 0\n",
    "        right = len(tokens)\n",
    "        ans = 0\n",
    "\n",
    "        while left < right:\n",
    "            if left == right:\n",
    "                break\n",
    "            if tokens[left] <= power and left < right:\n",
    "                ans += 1\n",
    "                power -= tokens[left]\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "                if ans > 0 and left < right:\n",
    "                    ans -= 1\n",
    "                    power += tokens[right]\n",
    "                else:\n",
    "                    break\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens.sort()\n",
    "        left = 0\n",
    "        right = len(tokens)\n",
    "        ans = 0\n",
    "\n",
    "        while left < right:\n",
    "            if tokens[left] <= power and left < right:\n",
    "                ans += 1\n",
    "                power -= tokens[left]\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "                if ans > 0 and left < right:\n",
    "                    ans -= 1\n",
    "                    power += tokens[right]\n",
    "                else:\n",
    "                    break\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens.sort()\n",
    "        left, right = 0, len(tokens) \n",
    "        cur_res = res = score = 0\n",
    "        while left < right:\n",
    "            if tokens[left] > power and cur_res <= 0:\n",
    "                break\n",
    "            if power >= tokens[left]:\n",
    "                cur_res += 1\n",
    "                power -= tokens[left]\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "                cur_res -= 1\n",
    "                power += tokens[right]\n",
    "            res = max(cur_res, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens.sort()\n",
    "        l, r, ans, cur = 0, len(tokens) - 1, 0, 0\n",
    "        while l <= r:\n",
    "            if power >= tokens[l]:\n",
    "                power -= tokens[l]\n",
    "                cur += 1\n",
    "                l += 1\n",
    "                ans = max(ans, cur)\n",
    "            elif cur > 0:\n",
    "                power += tokens[r]\n",
    "                cur -= 1\n",
    "                r -= 1\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens.sort()\n",
    "        l = 0\n",
    "        r = len(tokens)-1\n",
    "        res = 0\n",
    "        ress = 0\n",
    "        while l<=r:\n",
    "            if power<tokens[l]:\n",
    "                if res>0 and l<r:\n",
    "                    res-=1\n",
    "                    power+=tokens[r]\n",
    "                    r-=1\n",
    "                else:\n",
    "                    return res\n",
    "            else:\n",
    "                power-=tokens[l]\n",
    "                res+=1\n",
    "                # ress = max(ress,res)\n",
    "                l+=1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens.sort()\n",
    "        cur = ans = 0\n",
    "        st, ed = 0, len(tokens) - 1\n",
    "        while st <= ed:\n",
    "            if tokens[st] <= power:\n",
    "                cur += 1\n",
    "                power -= tokens[st]\n",
    "                st += 1\n",
    "                ans = max(cur, ans)\n",
    "            elif cur > 0:\n",
    "                power += tokens[ed]\n",
    "                cur -= 1\n",
    "                ed -= 1\n",
    "            else: return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\r\n",
    "        i, j, res, m = 0, len(tokens) - 1, 0, 0\r\n",
    "        tokens.sort()\r\n",
    "        if j < 0 or power < tokens[0]:\r\n",
    "            return 0\r\n",
    "        while i <= j:\r\n",
    "            if power >= tokens[i]:\r\n",
    "                res, power, i = res + 1, power - tokens[i], i + 1\r\n",
    "            elif power < tokens[i] and res >= 1 and j > i:\r\n",
    "                res, power, j = res - 1, power + tokens[j], j - 1\r\n",
    "            else:\r\n",
    "                break\r\n",
    "        return res\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        # 排序然后两端双指针，有能量就用，从最小的开始\n",
    "        # 能量没了就用分去换最大的能量\n",
    "        tokens.sort()\n",
    "        n = len(tokens)\n",
    "        if n==0: return 0\n",
    "        if n<=2: return 1 if power>=tokens[0] else 0\n",
    "        if power<tokens[0]:\n",
    "            return 0\n",
    "        res = 0\n",
    "        l,r = 0,n-1\n",
    "        while l<=r:\n",
    "            if power>=tokens[l]:\n",
    "                res+=1\n",
    "                power -= tokens[l]\n",
    "                l+=1\n",
    "            else:\n",
    "                if r-l>1:\n",
    "                    res -= 1\n",
    "                    power += tokens[r]\n",
    "                    r-=1\n",
    "                else:\n",
    "                    break\n",
    "            pass\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        n = len(tokens)\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if n==1:\n",
    "            return 1 if power>=tokens[0] else 0\n",
    "        tokens.sort()\n",
    "        if power<tokens[0]:\n",
    "            return 0\n",
    "        res = 0\n",
    "        index = 0\n",
    "        e = n-1\n",
    "        cur = 0\n",
    "        while index<=e:\n",
    "            flag = False\n",
    "            #表示无法再拿令牌\n",
    "            i = index\n",
    "            while power>=tokens[i] and i<=e:\n",
    "                power-=tokens[i]\n",
    "                cur+=1\n",
    "                res = max(res,cur)\n",
    "                i+=1\n",
    "                flag = True\n",
    "            if not flag:\n",
    "                #尝试去拿后面令牌\n",
    "                if cur>0:\n",
    "                    e-=1\n",
    "                    power+=tokens[e+1]\n",
    "                    cur-=1\n",
    "            else:\n",
    "                index=i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens.sort()\n",
    "        l = 0\n",
    "        r = len(tokens)-1\n",
    "        res = 0\n",
    "        ress = 0\n",
    "        while l<=r:\n",
    "            if power<tokens[l]:\n",
    "                if res>0:\n",
    "                    res-=1\n",
    "                    power+=tokens[r]\n",
    "                    r-=1\n",
    "                else:\n",
    "                    return res\n",
    "            else:\n",
    "                power-=tokens[l]\n",
    "                res+=1\n",
    "                ress = max(ress,res)\n",
    "                l+=1\n",
    "        \n",
    "        return ress"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        n = len(tokens)\n",
    "        if n < 1:\n",
    "            return 0\n",
    "\n",
    "        tokens.sort()\n",
    "        if power < tokens[0]:\n",
    "            return 0\n",
    "\n",
    "        res = 0\n",
    "        l = 0\n",
    "        while tokens[l] == 0:\n",
    "            res += 1\n",
    "            l += 1\n",
    "\n",
    "        r = n - 1\n",
    "        while l < r:\n",
    "            if power >= tokens[l]:\n",
    "                power -= tokens[l]\n",
    "                res += 1\n",
    "                l += 1\n",
    "                continue\n",
    "            if res > 0:\n",
    "                res -= 1\n",
    "                power += tokens[r]\n",
    "                r -= 1\n",
    "\n",
    "        if power >= tokens[l]:\n",
    "            res += 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens.sort()\n",
    "        deque = collections.deque(tokens)\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        while deque and (power >= deque[0] or cur > 0):\n",
    "            while deque and power >= deque[0]:\n",
    "                power -= deque.popleft()\n",
    "                cur += 1\n",
    "            ans = max(ans, cur)\n",
    "\n",
    "            if deque and cur > 0:\n",
    "                power += deque.pop()\n",
    "                cur -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens = sorted(tokens)\n",
    "        if not tokens:\n",
    "            return 0\n",
    "        if power < tokens[0]:\n",
    "            return 0\n",
    "\n",
    "        left = 0\n",
    "        right = len(tokens) - 1\n",
    "        outcome = 0\n",
    "        while left <= right:\n",
    "            if power >= tokens[left]:\n",
    "                power -= tokens[left]\n",
    "                outcome += 1\n",
    "                left += 1\n",
    "            elif outcome > 0 and left < right:\n",
    "                    outcome -= 1\n",
    "                    power += tokens[right]\n",
    "                    right -= 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return outcome\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        n = len(tokens)\n",
    "        if n < 1:\n",
    "            return 0\n",
    "\n",
    "        tokens.sort()\n",
    "        if power < tokens[0]:\n",
    "            return 0\n",
    "\n",
    "        res = 0\n",
    "        l = 0\n",
    "        while tokens[l] == 0:\n",
    "            res += 1\n",
    "            l += 1\n",
    "\n",
    "        r = n - 1\n",
    "        while l < r:\n",
    "            if power >= tokens[l]:\n",
    "                power -= tokens[l]\n",
    "                res += 1\n",
    "                l += 1\n",
    "                continue\n",
    "            if res > 0:\n",
    "                res -= 1\n",
    "                power += tokens[r]\n",
    "                r -= 1\n",
    "\n",
    "        if power >= tokens[l]:\n",
    "            res += 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens.sort()\n",
    "        n = len(tokens)\n",
    "        ret = 0\n",
    "        l = 0\n",
    "        r = n - 1\n",
    "        score = 0\n",
    "        while l <= r:\n",
    "            if power >= tokens[l]:\n",
    "                score += 1\n",
    "                power -= tokens[l]\n",
    "                l += 1\n",
    "            elif score > 0:\n",
    "                score -= 1\n",
    "                power += tokens[r]\n",
    "                r -= 1\n",
    "            else:\n",
    "                break\n",
    "            ret = max(ret, score)\n",
    "        return ret\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens.sort()\n",
    "        left, right = 0, len(tokens)-1\n",
    "        maxScore = score = 0\n",
    "        while left <= right:\n",
    "            if power < tokens[left] and score <= 0:\n",
    "                return maxScore\n",
    "            else:\n",
    "                if power >= tokens[left]:\n",
    "                    power -= tokens[left]\n",
    "                    left += 1\n",
    "                    maxScore = max(maxScore, score := score + 1)\n",
    "                else:\n",
    "                    while score > 0 and power < tokens[left]:\n",
    "                        power += tokens[right]\n",
    "                        right -= 1\n",
    "                        score -= 1\n",
    "        return maxScore\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens.sort()\n",
    "        n = len(tokens)\n",
    "        psum = [0] * (n + 1)\n",
    "        for i in range(n): psum[i+1] = psum[i] + tokens[i]\n",
    "\n",
    "        def f(L, R, P):\n",
    "            l, r = L, R + 1\n",
    "            while l + 1 < r:\n",
    "                mid = (l + r) // 2\n",
    "                if psum[mid] - psum[L] <= P:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid\n",
    "            return l - L\n",
    "\n",
    "        l, r = 0, n\n",
    "        maxScore = 0\n",
    "        while l < r:\n",
    "            maxScore = max(maxScore, f(l, r, power))\n",
    "            if power >= tokens[l]:\n",
    "                power = power - tokens[l] + tokens[r-1]\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return maxScore\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\r\n",
    "        i, j, res, m = 0, len(tokens) - 1, 0, 0\r\n",
    "        tokens.sort()\r\n",
    "        if j < 0 or power < tokens[0]:\r\n",
    "            return 0\r\n",
    "        while i <= j:\r\n",
    "            if power >= tokens[i]:\r\n",
    "                res, power, i = res + 1, power - tokens[i], i + 1\r\n",
    "                m = max(m, res)\r\n",
    "            elif power < tokens[i] and res >= 1:\r\n",
    "                res, power, j = res - 1, power + tokens[j], j - 1\r\n",
    "            else:\r\n",
    "                break\r\n",
    "        return m\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens.sort()\n",
    "        deque = collections.deque(tokens)\n",
    "        ans = bns = 0\n",
    "        while deque and (power >= deque[0] or bns):\n",
    "            while deque and power >= deque[0]:\n",
    "                power -= deque.popleft()\n",
    "                bns += 1\n",
    "            ans = max(ans, bns)\n",
    "            if deque and bns:\n",
    "                power += deque.pop()\n",
    "                bns -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        if not tokens:\n",
    "            return 0\n",
    "        tokens.sort()\n",
    "        if tokens[0]>power:\n",
    "            return 0\n",
    "        n=len(tokens)\n",
    "        i,j=0,n-1\n",
    "        ans=0\n",
    "        now=0\n",
    "        while i<=j:\n",
    "            #print(i,j,power,tokens[i])\n",
    "            if power>=tokens[i]:\n",
    "                now+=1\n",
    "                ans=max(ans,now)\n",
    "                power-=tokens[i]\n",
    "                i+=1\n",
    "            else:\n",
    "                now-=1\n",
    "                power+=tokens[j]\n",
    "                j-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        if not tokens:\n",
    "            return 0\n",
    "        tokens.sort()\n",
    "        if power < tokens[0]:\n",
    "            return 0\n",
    "        score = 0\n",
    "        left, right = 0, len(tokens) - 1\n",
    "        while left < right:\n",
    "            if power >= tokens[left]:\n",
    "                power -= tokens[left]\n",
    "                score += 1\n",
    "                left += 1\n",
    "            elif score >= 1:\n",
    "                score -= 1\n",
    "                power += tokens[right]\n",
    "                right -= 1\n",
    "        if power >= tokens[left]:\n",
    "            score += 1\n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "由于要获取能量，只需要一分，所以可以用最少的能量换取分，然后再换取足量的能量\n",
    "最后再换成分。\n",
    "对令牌排序，大致可以将令牌分为3部分，左边的部分是换取启动分用的\n",
    "右边是换取能量用的，中间是尽量将能量换取分\n",
    "进一步地，左边和中间都是换分的，右边是换能量的\n",
    "换分总能量是右边的加上起始的\n",
    "要换取最多分，那需要在左边和中间的能量 大于等于 换分总能量 \n",
    "的情况下，两边的能量尽可能接近\n",
    "实现的话，可以模拟换分和换能量的过程\n",
    "相向双指针，左指针换分，右指针换能量\n",
    "只有没法不够能量换分的情况下才去换能量\n",
    "最后，还要避免换了能量后，没有多余的令牌来换分\n",
    "每次取score的最值即可\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        n = len(tokens)\n",
    "        tokens.sort()\n",
    "        l, r = 0, n-1\n",
    "        score = 0\n",
    "        ans = 0\n",
    "        while l<=r:\n",
    "            if power >= tokens[l]:\n",
    "                power -= tokens[l]\n",
    "                score += 1\n",
    "                l+=1\n",
    "            elif score > 0:\n",
    "                power += tokens[r]\n",
    "                score -= 1\n",
    "                r-=1\n",
    "            else:\n",
    "                break\n",
    "            ans = max(ans, score)\n",
    "            # print('l:{}, r:{}, power:{}, score:{}'.format(l, r, power, score))\n",
    "\n",
    "        # print('l:{}, r:{}, power:{}, score:{}'.format(l, r, power, score))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        # # 一眼动态规划 0-1背包类的\n",
    "        # # power有关的，以及目前tokens的状态二者决定\n",
    "\n",
    "        # # 我隐约感觉我当前的选择是和后面的东西有关的\n",
    "        # # 前i个令牌,j个power\n",
    "        # if j > tokens[i]:\n",
    "        #     # 可以选择分数加一，power\n",
    "        #     dp[i][j] = dp[i-1][j-tokens[i]] + 1\n",
    "        # # 或者什么也不做\n",
    "        # dp[i][j] = dp[i-1][j] + dp2[i+1]\n",
    "        # # 或者\n",
    "        # dp[i][j] = dp2[i+1][j+power]\n",
    "        # # 排序\n",
    "        # tokens.sort()\n",
    "        # @cache \n",
    "        # def dp(i,j,power):\n",
    "        #     print(i,j,power)\n",
    "        #     # 最后条件\n",
    "        #     if i > j:\n",
    "        #         return 0 \n",
    "        #     if i == j:\n",
    "        #         if tokens[i] < power:\n",
    "        #             return 1\n",
    "        #         else:\n",
    "        #             return 0 \n",
    "        #     # 若不升了\n",
    "        #     res = 0\n",
    "        #     # 二分\n",
    "        #     a = power\n",
    "        #     left = i \n",
    "        #     while left <= j and a > tokens[left]:\n",
    "        #         res += 1\n",
    "        #         a -= tokens[left]\n",
    "        #         left += 1\n",
    "            \n",
    "        #     # 若还要升\n",
    "        #     res = max(res,dp(i+1,j-1,power+tokens[j]-tokens[0]))\n",
    "        #     return res \n",
    "        # return dp(0,len(tokens)-1,power)\n",
    "        \n",
    "        def cual(i,j,power):\n",
    "            res = 0\n",
    "            while i <= j and power >= tokens[i]:\n",
    "                res += 1\n",
    "                power -= tokens[i]\n",
    "                i += 1\n",
    "            return res\n",
    "        \n",
    "        tokens.sort()\n",
    "        res = cual(0,len(tokens)-1,power)\n",
    "        curpower = power\n",
    "        for i in range(len(tokens)):\n",
    "            if curpower > tokens[i] and i < len(tokens)-i-1:\n",
    "                curpower = tokens[len(tokens)-i-1] - tokens[i] + curpower\n",
    "                res = max(res,cual(i+1,len(tokens)-i-2,curpower))\n",
    "            else:\n",
    "                break\n",
    "        return res\n",
    "        # prefix = [0]*(len(tokens)+1)\n",
    "        # for i in range(1,len(prefix)):\n",
    "        #     prefix[i] = prefix[i-1] + tokens[i-1]\n",
    "        # res = 0\n",
    "        # for i in range(len(tokens)):\n",
    "        #     curpower = power - prefix[i] + prefix[-1] - prefix[len(prefix)-1-i]\n",
    "        #     # print(i,len(tokens)-i-1,curpower)\n",
    "        #     if cual(i,len(tokens)-i-1,curpower) == 0:\n",
    "        #         break \n",
    "        #     res = max()\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens = sorted(tokens)\n",
    "        if len(tokens) == 0:\n",
    "            return 0\n",
    "        score = 0\n",
    "        i = 0\n",
    "        j = len(tokens)\n",
    "        while i < j:\n",
    "            token = tokens[i]\n",
    "            if power >= token:\n",
    "                score += 1\n",
    "                power -= token\n",
    "                i += 1\n",
    "            else:\n",
    "                if j - 1 <= i or score <= 0:\n",
    "                    break\n",
    "                score -= 1\n",
    "                power += tokens[j - 1]\n",
    "                j -= 1\n",
    "        return score\n",
    "        \n",
    "\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        if not tokens:\n",
    "            return 0\n",
    "        tokens.sort()\n",
    "        score = 0\n",
    "        left, right = 0, len(tokens) - 1\n",
    "        max_score = 0\n",
    "        while left <= right:\n",
    "            if power >= tokens[left]:\n",
    "                power -= tokens[left]\n",
    "                score += 1\n",
    "                left += 1\n",
    "                max_score = max(max_score, score)\n",
    "            elif score >= 1:\n",
    "                score -= 1\n",
    "                power += tokens[right]\n",
    "                right -= 1\n",
    "            else:\n",
    "                break\n",
    "    \n",
    "        return max_score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect \n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens.sort()\n",
    "        n = len(tokens)\n",
    "        pre = [0] * (n+1) \n",
    "        for i in range(1, n+1):\n",
    "            pre[i] = pre[i-1] + tokens[i-1]\n",
    "\n",
    "        l = 0 \n",
    "        profit = bisect.bisect_left(pre, power + 1) - 1\n",
    "        mx = profit\n",
    "        if profit == 0:\n",
    "            return 0 \n",
    "        for i in range(n-1, -1, -1):\n",
    "            idx = bisect.bisect_left(pre, tokens[i] + power + 1) - 1\n",
    "            #print(idx, profit) \n",
    "            if idx - l - 1 >= profit:\n",
    "                profit = idx - l - 1 \n",
    "                power += tokens[i] \n",
    "                l += 1\n",
    "                mx = max(mx, profit) \n",
    "            else:\n",
    "                break \n",
    "        return mx \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        def cual(i,j,power):\n",
    "            res = 0\n",
    "            while i <= j and power >= tokens[i]:\n",
    "                res += 1\n",
    "                power -= tokens[i]\n",
    "                i += 1\n",
    "            return res\n",
    "        \n",
    "        tokens.sort()\n",
    "        res = cual(0,len(tokens)-1,power)\n",
    "        curpower = power\n",
    "        for i in range(len(tokens)):\n",
    "            if curpower > tokens[i] and i < len(tokens)-i-1:\n",
    "                curpower = tokens[len(tokens)-i-1] - tokens[i] + curpower\n",
    "                res = max(res,cual(i+1,len(tokens)-i-2,curpower))\n",
    "            else:\n",
    "                break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens.sort() \n",
    "        n = len(tokens) \n",
    "        pre = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            pre[i] = pre[i-1] + tokens[i-1]\n",
    "        idx = bisect.bisect_left(pre, power+1) - 1\n",
    "        ans = idx \n",
    "        if ans == 0:\n",
    "            return 0 \n",
    "        j = 0 \n",
    "        for i in range(n-1, 0, -1):\n",
    "            power += tokens[i]\n",
    "            j += 1\n",
    "            idx = bisect.bisect_left(pre, power+1, 0, i+1) - 1\n",
    "            #print(idx) \n",
    "            ans = max(ans, idx - j) \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        score = mScore = 0\n",
    "        n = len(tokens)\n",
    "        tokens.sort()\n",
    "        l,r = 0,n-1\n",
    "        while l<=r:\n",
    "            if power >= tokens[l]:\n",
    "                power -= tokens[l]\n",
    "                l += 1\n",
    "                score +=1\n",
    "                mScore = max(mScore,score)  \n",
    "            else:\n",
    "                if score>0:\n",
    "                    score -=1\n",
    "                    power += tokens[r]\n",
    "                    r -=1\n",
    "                else:\n",
    "                    break\n",
    "        return mScore\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        tokens.sort()\n",
    "        l=0\n",
    "        r=len(tokens)-1\n",
    "        points=0\n",
    "        while l<r:\n",
    "            if power>=tokens[l]:\n",
    "                power-=tokens[l]\n",
    "                l+=1\n",
    "                points+=1\n",
    "            elif power<tokens[l] and points>0:\n",
    "                points-=1\n",
    "                power+=tokens[r]\n",
    "                r=r-1\n",
    "            else:\n",
    "                break\n",
    "        #print(power,points,l,r,tokens[l])\n",
    "        if l==r and power>=tokens[l]:\n",
    "            print(10)\n",
    "            points+=1\n",
    "\n",
    "\n",
    "        return points\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\r\n",
    "        i, j, res, m = 0, len(tokens) - 1, 0, 0\r\n",
    "        tokens.sort()\r\n",
    "        while i <= j:\r\n",
    "            if power >= tokens[i]:\r\n",
    "                res, power, i = res + 1, power - tokens[i], i + 1\r\n",
    "                m = max(m, res)\r\n",
    "            elif power < tokens[i] and res >= 1:\r\n",
    "                res, power, j = res - 1, power + tokens[j], j - 1\r\n",
    "            else:\r\n",
    "                break\r\n",
    "        return m\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\r\n",
    "        i, j, res, m = 0, len(tokens) - 1, 0, 0\r\n",
    "        tokens.sort()\r\n",
    "        while i <= j:\r\n",
    "            if power >= tokens[i]:\r\n",
    "                res, power, i = res + 1, power - tokens[i], i + 1\r\n",
    "                m = max(m, res)\r\n",
    "            elif power < tokens[i] and res >= 1:\r\n",
    "                res, power, j = res - 1, power + tokens[j], j - 1\r\n",
    "            else:\r\n",
    "                break\r\n",
    "        return m\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        n = len(tokens)\n",
    "        if n < 1:\n",
    "            return 0\n",
    "\n",
    "        tokens.sort()\n",
    "        if power < tokens[0]:\n",
    "            return 0\n",
    "\n",
    "        res = 0\n",
    "        l = 0\n",
    "        while tokens[l] == 0:\n",
    "            res += 1\n",
    "            l += 1\n",
    "\n",
    "        r = n - 1\n",
    "        while l < r:\n",
    "            if power >= tokens[l]:\n",
    "                power -= tokens[l]\n",
    "                res += 1\n",
    "                l += 1\n",
    "                continue\n",
    "            if res > 0:\n",
    "                res -= 1\n",
    "                power += tokens[r]\n",
    "                r -= 1\n",
    "\n",
    "        if power >= tokens[l]:\n",
    "            res += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:\n",
    "        n, score = len(tokens), 0\n",
    "        if n == 0: return 0\n",
    "        tokens.sort()\n",
    "        left, right = 0, n - 1\n",
    "        while left <= right:\n",
    "            if score > 0:\n",
    "                power += tokens[right]\n",
    "                right -= 1\n",
    "                score -= 1\n",
    "            if left > right or tokens[left] > power: break\n",
    "            while left <= right and tokens[left] <= power:\n",
    "                score += 1\n",
    "                power -= tokens[left]\n",
    "                left += 1\n",
    "        while left < n and tokens[left] <= power:\n",
    "            power -= tokens[left]\n",
    "            score += 1\n",
    "            left += 1\n",
    "        return score\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
